package July;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
import java.util.logging.Level;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author:gao
 * @date:2020/7/4
 * @time:8:47
 * @version:0.0.1
 * @description:none
 */


//32. 最长有效括号
//public class LongestValidParentheses {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        solution.longestValidParentheses("()");
//    }
//}
//

//dp解法
//class Solution {
//    public int longestValidParentheses(String s) {
//        int maxans = 0;
//        int dp[] = new int[s.length()];
//        for (int i = 1; i < s.length(); i++) {
//            if (s.charAt(i) == ')') {
//                if (s.charAt(i - 1) == '(') {
//                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
//                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
//                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
//                }
//                maxans = Math.max(maxans, dp[i]);
//            }
//        }
//        return maxans;
//    }
//}


/**
 * 栈版本
 * 服了
 */
class Solution12 {
    public int longestValidParentheses(String s) {

        LinkedList<Integer> stack =new LinkedList<>();
        int max =0;
        //先放个-1，表示上一个未被匹配的是-1,方便计算
        stack.push(-1);
        for (int i = 0; i <s.length() ; i++) {
            char c = s.charAt(i);
            //直接进栈
            if(c=='('){
                stack.push(i);
            }else{
                int index = stack.pop();
                //如果出栈后是空，代表上次出栈的是）的位置，把i入站，作为栈底
                if(stack.isEmpty()){
                    stack.push(i);
                }else{//代表本次出战的是（,计算长度
                    max = Math.max(i-stack.peek(),max);
                }
            }
        }
        return max;
    }
}